package leetcode.hot100;

public class Solution5 {

    public static void main(String[] args) {
        Solution5 solu = new Solution5();
        String s = "babad";
        System.out.println(solu.longestPalindrome(s));
    }

    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int maxLen = 0, start = 0, end = 0; //记录最长回文串
        //dp
        for(int j=0;j<s.length();j++){
            for(int i=0;i<=j;i++){
                if(s.charAt(i)==s.charAt(j) && (j-i<3||dp[i+1][j-1])){
                    dp[i][j] = true;
                    //记录
                    if(maxLen<j-i+1){
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start,end+1);
    }
}
